package Middle.WordsMaze;

public class WordsMaze_Optimize {
    public static void main(String[] args) {
        char[][] grids = new char[][]{
                new char[]{'A', 'B', 'C', 'E'},
                new char[]{'S', 'F', 'C', 'S'},
                new char[]{'A', 'D', 'E', 'E'},
                new char[]{'H', 'E', 'R', 'N'},
                new char[]{'U', 'I', 'O', 'P'}
        };
        String target = "ABCCE";
        System.out.println(wordPuzzle(grids, target));
    }

    public static Boolean wordPuzzle(char[][] grids, String target) {
        if (grids == null || grids.length == 0 || grids[0].length == 0 || target.isEmpty()) return false;
        for (int i = 0; i < grids.length; i++) {
            for (int j = 0; j < grids[0].length; j++) {
                if (dfs(grids, target, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(char[][] grids, String word, int row, int col, int index) {
        if (index == word.length()) {
            return true;
        }
        boolean isBounding = row < 0 || row >= grids.length || col < 0 || col >= grids[0].length;
        if (isBounding || grids[row][col] != word.charAt(index)) {
            return false;
        }
        //取回值暂存
        char temp = grids[row][col];
        //用一个特殊字符占用，这个字符不会出现在grids里面才行
        grids[row][col] = '#';

        boolean found = dfs(grids, word, row + 1, col, index + 1) ||
                dfs(grids, word, row - 1, col, index + 1) ||
                dfs(grids, word, row, col + 1, index + 1) ||
                dfs(grids, word, row, col - 1, index + 1);
        //恢复原值
        grids[row][col] = temp;
        return found;
    }

}
